
/*
 * Question: Try to propose a recursive algorithm
 * to calculate, in a binary tree, the depth of the
 * subtree which is rooted at a node whose value is 'x'.
 */

#include <iostream>
#include "bitree.h"
using namespace std;

class bitree : public _bitree<bitree, char>{};

int depthx(bitree *rt, char x, int &d)
{
    int depth;
    int ld, rd;

    if (!rt){
        d = 0;
        return 0;
    }
    depth = depthx(rt->lchild, x, ld);
    if (depth > 0)
        return depth;
    depth = depthx(rt->rchild, x, rd);
    if (depth > 0)
        return depth;
    d = (ld>rd ? ld : rd)+1;
    if (rt->key == x)
        return d;
    else
        return 0;
}

int main()
{
    bitree *rt;
    int depth, d;

    bitree_create<bitree, char>(rt, "ex44.txt");
    depth = depthx(rt, 'G', d);
    if (!depth)
        cout << "Not found." << endl;
    else
        cout << depth << endl;
    bitree_destory(rt);

    return 0;
}
